import java.util.Iterator;

public class RandomQueue<Item> implements Iterable<Item>
{
    private Item[] items;      //The array of items in the queue
    private int N;             //The number of elements
    
    /**
     * Nested class
     *
     * The iterator of the randomqueue
     */
    private class RandomQueueIterator implements Iterator<Item>
    {
        int k = 0;                              //Number of elements in alreadyTaken        
        int alreadyTaken[] = new int[N];        //All the items already taken
        
        /**
         * Remove is not used, but need to be implemented, as we implements from Iterator
         */
        public void remove() {}
        
        /**
         * @return true if there is more elements in the queue
         */
        public boolean hasNext() {
            return k < N;
        }
        
        /**
         * @return The next random item in the queue
         */
        public Item next()
        {
            boolean newOne = true;
            int j = 0;
            
            do
            {
                newOne = true;
                j = StdRandom.uniform(N);
                for(int i = 0; i < k; i++)
                    newOne = newOne && j != alreadyTaken[i];
                       
            }while(!newOne);
            alreadyTaken[k++] = j;
            
            return items[j];
        }
    }
    
    /**
     * Default constructor
     */
    public RandomQueue()
    {
        items = (Item[]) new Object[1];
        N = 0;
    }
    
    /**
     * @return true if there isn't any elements left in the queue
     */
    public boolean isEmpty() 
    {
        return N == 0;
    }
    
    /**
     * Returns the number of elements currently in the queue
     */
    public int size() 
    {
        return N;
    }
    
    /**
     * Rebuilds the array, with allocation equals to 
     * number of elements times 2
     */
    public void rebuild() 
    {
        Item[] tmp = (Item[]) new Object[N*2];
        for(int i = 0; i < N; i++)
            tmp[i] = items[i];
        items = tmp;
    }
    
    /**
     * Enqueue an item into the array
     */
    public void enqueue(Item item)
    {
        items[N] = item;
        N++;
        if(N == items.length)
            rebuild();   
    }
    
    /**
     * Return a random sample from the queue
     * The element stays in the queue
     * @return a random element from the queue
     */
    public Item sample() throws RuntimeException
    {
        if(N == 0)
            throw new RuntimeException("The queue is empty!");
        
        return items[StdRandom.uniform(N)];
    }
    
    /**
     * Return a random element from the queue, and 
     * delete it from the queue
     * @return A random element from the queue
     */
    public Item dequeue() throws RuntimeException 
    {
        if(N == 0)
            throw new RuntimeException("The queue is empty!");
        
        int x = StdRandom.uniform(N);
        Item returnItem = items[x];
        
        for(int i = x; i < N; i++)
        {
            items[i] = items[i+1];
        }
        
        items[--N] = null;
        
        if(N <= items.length/4)
        {
            rebuild();
        }
      
        return returnItem;
    }
    
    /**
     * @return An iterator to loop through the queue
     */
    public Iterator<Item> iterator() 
    {
        return new RandomQueueIterator();
    }
}